package org.demo.algorithm;
/**
 * 用回溯法计算全排列
 * @author  
 * @date    2010-9-14
 * @file    org.demo.algorithm.FullSort2.java
 */
public class FullSort2 {
	/**
	 * 测试 
	 * @param args
	 */
	public static void main(String[] args) {
		int[] data = new int[]{1,2,3,4};
		backtrack(0,data.length,data);
	}
	
	/**
	 * 回溯法求全排列
	 * @param curIndex
	 * @param max
	 * @param data
	 */
	public static void backtrack(int curIndex,int max,int[] data){
		if(curIndex >= max){
			output(data);
			return;
		}
		for(int i=curIndex; i<max; i++){
			swap(data,curIndex,i);
			backtrack(curIndex+1,max,data);
			swap(data,curIndex,i);
		}
	}
	/**
	 * 交换数据
	 * @param data
	 * @param curIndex
	 * @param i
	 */
	private static void swap(int[] data, int curIndex, int i) {
		int tmp = data[curIndex];
		data[curIndex] = data[i];
		data[i] = tmp;
	}
	/**
	 * 输出
	 * @param data
	 */
	private static void output(int[] data) {
		for(int i=0;i<data.length;i++){
			System.out.print(data[i] + " ");
		}
		System.out.println();
	}
}
